﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace tp1
{
    public class Labyrinthe
    {
        private const int CONSTANTE_ALGORITHME = 4;
        private const int MIN_RANDOM_VALUE = 1;
        private const int MAX_RANDOM_VALUE = 20;

        private int n;
        private int m;

        private int opGenGraphe;
        private int opPrim;
        private int opAffichage;

        public int OpGenGraphe
        {
            get { return opGenGraphe; }
        }

        public int OpPrim
        {
            get { return opPrim; }
        }

        public int OpAffichage
        {
            get { return opAffichage; }
        }

        private bool[] nodes;
        private int[,] links;

        private Bitmap bmLabyrinthe;

        private Labyrinthe(int n, int m)
        {
            this.n = n;
            this.m = m;

            this.nodes = new bool[n * m];
            this.links = new int[this.nodes.Length, CONSTANTE_ALGORITHME];

            this.opGenGraphe = 0;
            this.opPrim = 0;
            this.opAffichage = 0;
        }

        public static Labyrinthe Create(int n, int m)
        {
            Labyrinthe newLabyrinthe = null;

            if (n < 2 || m < 2)
                throw new ArgumentOutOfRangeException("La taille nécessaire pour la génération d'un labyrinthe doit être supérieur à 2x2.");

            newLabyrinthe = new Labyrinthe(n, m);
            newLabyrinthe.GenerateRandomLinksValue();
            Console.WriteLine("Graphe généré: " + newLabyrinthe.opGenGraphe + " op.");

            newLabyrinthe.Prim();
            Console.WriteLine("Arbre minimal calculée avec Prim: " + newLabyrinthe.opPrim + " op.");

            return newLabyrinthe;
        }

        private void GenerateRandomLinksValue()
        {
            Coordinates adjugateCoordinates;
            Random random = new Random();

            for (int x = 0; x < nodes.Length; x++)
                for (int y = 0; y < CONSTANTE_ALGORITHME / 2; y++)
                {
                    adjugateCoordinates = GetAdjugateCoordinates(new Coordinates(x, y));
                    opGenGraphe++;
                    if (adjugateCoordinates != null)
                    {
                        links[x, y] = random.Next(MIN_RANDOM_VALUE, MAX_RANDOM_VALUE);
                        links[adjugateCoordinates.X, adjugateCoordinates.Y] = links[x, y];
                        opGenGraphe += 2;
                    }
                }
        }

        private Coordinates GetAdjugateCoordinates(Coordinates coordinate)
        {
            Coordinates adjugateCoordinates = null;

            switch (coordinate.Y)
            {
                case 0:
                    if ((coordinate.X - m >= 0))
                        adjugateCoordinates = new Coordinates(coordinate.X - m, 3);
                    break;
                case 1:
                    if (!(coordinate.X % m == 0))
                        adjugateCoordinates = new Coordinates(coordinate.X - 1, 2);
                    break;
                case 2:
                    if (!(coordinate.X % m == m - 1))
                        adjugateCoordinates = new Coordinates(coordinate.X + 1, 1);
                    break;
                case 3:
                    if (coordinate.X + m < nodes.Length)
                        adjugateCoordinates = new Coordinates(coordinate.X + m, 0);
                    break;
            }
            opPrim++;
            return adjugateCoordinates;
        }

        private void Prim()
        {
            List<Coordinates> linksCoordinate = new List<Coordinates>();
            int xIndex;
            int currentValue;

            int minValue;
            Coordinates minCoordinates = null;
            Coordinates minAdjugateCoordinates = null;

            Coordinates newCoordinates = null;
            Coordinates adjugateCoordinates = null;


            xIndex = Array.FindIndex(nodes, n => !n);

            nodes[xIndex] = true;

            opPrim += 2;

            for (int y = 0; y < CONSTANTE_ALGORITHME; y++)
                if (links[xIndex, y] >= MIN_RANDOM_VALUE)
                {
                    linksCoordinate.Add(new Coordinates(xIndex, y));
                    opPrim++;
                }
            do
            {
                minValue = MAX_RANDOM_VALUE + 1;

                foreach (Coordinates coordinate in linksCoordinate)
                {
                    adjugateCoordinates = GetAdjugateCoordinates(coordinate);
                    if (!nodes[adjugateCoordinates.X])
                    {
                        currentValue = links[coordinate.X, coordinate.Y];
                        opPrim++;
                        if (currentValue >= MIN_RANDOM_VALUE && currentValue < minValue)
                        {
                            minCoordinates = coordinate;
                            minValue = currentValue;
                            opPrim += 2;
                        }
                    }
                    opPrim++;
                }

                links[minCoordinates.X, minCoordinates.Y] = MIN_RANDOM_VALUE - 2;
                minAdjugateCoordinates = GetAdjugateCoordinates(minCoordinates);
                links[minAdjugateCoordinates.X, minAdjugateCoordinates.Y] = links[minCoordinates.X, minCoordinates.Y];

                if (linksCoordinate.Any(s => s.Equals(minCoordinates)))
                {
                    linksCoordinate.Remove(minCoordinates);
                    opPrim++;
                }
                if (linksCoordinate.Any(c => c.Equals(minAdjugateCoordinates)))
                {
                    linksCoordinate.Remove(minAdjugateCoordinates);
                    opPrim++;
                }

                xIndex = minAdjugateCoordinates.X;

                nodes[xIndex] = true;
                if (!nodes.Any(n => !n))
                    break;

                for (int y = 0; y < CONSTANTE_ALGORITHME; y++)
                    if (links[xIndex, y] >= MIN_RANDOM_VALUE)
                    {
                        newCoordinates = new Coordinates(xIndex, y);
                        adjugateCoordinates = GetAdjugateCoordinates(newCoordinates);
                        opPrim += 2;
                        if (!nodes[adjugateCoordinates.X])
                        {
                            linksCoordinate.Add(newCoordinates);
                            opPrim++;
                        }
                    }

                linksCoordinate.RemoveAll(c => nodes[GetAdjugateCoordinates(c).X]);
                opPrim += 7;
            } while (true);
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public override string ToString()
        {
            string result = String.Empty;
            result += String.Format("[n = {0}, m = {1}]\n", n, m);

            result += "    ";
            for (int x = 0; x < nodes.Length; x++)
            {
                result += x.ToString().PadLeft(3, ' ');
            }

            result += "\n";

            for (int y = 0; y < 4; y++)
            {
                switch(y)
                {
                    case 0: result += "-m |"; break;
                    case 1: result += "-1 |"; break;
                    case 2: result += "+1 |"; break;
                    case 3: result += "+m |"; break;
                }

                for (int x = 0; x < nodes.Length; x++)
                {
                    result += links[x, y].ToString().PadLeft(3, ' ');
                }
                result += "\n";
            }

            return result;
        }

        public Bitmap GetBitmap()
        {
            if (bmLabyrinthe == null)
            {
                int pathSize = 16;
                int outerWall = pathSize / 2;
                int width = (m * 2 - 1);
                int height = (n * 2 - 1);

                bmLabyrinthe = new Bitmap(width * pathSize + (outerWall * 2), height * pathSize + (outerWall * 2));
                Graphics graphics = Graphics.FromImage(bmLabyrinthe);

                graphics.FillRectangle(Brushes.DarkGray, 0, 0, bmLabyrinthe.Width, bmLabyrinthe.Height);

                GraphicsPath path = new GraphicsPath();

                Point currentPosition;
                Size cellSize = new Size(pathSize, pathSize);
                opAffichage ++;
                for (int x = 0; x < nodes.Length; x++)
                {
                    currentPosition = new Point(((x % m) * 2 * pathSize) + outerWall, ((int)(Math.Floor((double)x / (double)m) * 2 * pathSize) + outerWall));
                    graphics.FillRectangle(Brushes.White, new Rectangle(currentPosition, cellSize));
                    if (links[x, 3] == -1)
                    {
                        graphics.FillRectangle(Brushes.White, new Rectangle(new Point(currentPosition.X, currentPosition.Y + pathSize), cellSize));
                        opAffichage++;
                    }
                    if (links[x, 2] == -1)
                    {
                        graphics.FillRectangle(Brushes.White, new Rectangle(new Point(currentPosition.X + pathSize, currentPosition.Y), cellSize));
                        opAffichage++;
                    }

                    if (x == 0)
                        graphics.FillRectangle(Brushes.White, new Rectangle(new Point(currentPosition.X - outerWall, currentPosition.Y), cellSize));
                    else if (x == nodes.Length - 1)
                        graphics.FillRectangle(Brushes.White, new Rectangle(new Point(currentPosition.X + outerWall, currentPosition.Y), cellSize));

                    opAffichage += 3;
                }
            }
            return bmLabyrinthe;
        }
    }
}
